package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if (p == nil && q != nil) || (p != nil && q == nil) {
		return false
	}
	queue1 := []*TreeNode{p}
	queue2 := []*TreeNode{q}
	for len(queue1) > 0 && len(queue2) > 0 {
		n1 := queue1[0]
		queue1 = queue1[1:]
		n2 := queue2[0]
		queue2 = queue2[1:]
		if n1 == nil && n2 == nil {
			continue
		}
		if (n1 == nil && n2 != nil) || (n1 != nil && n2 == nil) {
			return false
		}
		if n1.Val != n2.Val {
			return false
		}
		queue1 = append(queue1, n1.Left, n1.Right)
		queue2 = append(queue2, n2.Left, n2.Right)
	}
	return true
}

func main() {
	p := &TreeNode{
		Val:  1,
		Left: &TreeNode{Val: 2},
	}
	q := &TreeNode{
		Val:  1,
		Left: &TreeNode{Val: 2},
	}
	println(isSameTree(p, q))
}
